#include <stdio.h>
#include <stdlib.h>

/*
 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

⒈ 从第一个元素开始，该元素可以认为已经被排序

⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描

⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置

⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⒌ 将新元素插入到下一位置中

⒍ 重复步骤2~5

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。

该算法可以认为是插入排序的一个变种，称为二分查找排序。
*/


/*
	输入参数中，需要排序的数组为array[ ]，起始索引为first（数组有序部分最后一个的下标，或者直接标 0），
	
	终止索引为last（数组元素的最后一个的下标）。示例代码的函数采用insert-place排序，调用完成后，
	
	array[]中从first到last处于升序排列。
 */
void insert(int array[], int first,int last)
{
  int i, j;
  int temp;

  for(i = first + 1; i < last; i++) {
    temp = array[i];
    j = i - 1;

    //与已排序的数逐一比较，大于temp时，该数移后
    while((j >= 0) && (array[j] > temp)) {
      array[j+1] = array[j];
      j--;
    }

    //存在大于temp的数
    if (j != i-1) {
      array[j+1] = temp;
    }
  }
}


void insert_better(int * array, unsigned int n)
{
  int i, j;
  int temp;

  for (i = 1; i < n; i++) {
      temp = *(array + i);
      for(j = i; j > 0 && *(array + j - 1) > temp; j--) {
	  *(array + j) = *(array + j - 1);
      }
      *(array + j) = temp;
    }
}

void display(int * src, int len)
{
  int i;
  
  for (i = 0; i < len; i++)
    printf(" %d ", src[i]);
  printf("\n\n");
}

int main()
{
  int src[8] = {3, 1, 5, 7, 2, 4, 9, 6};
  
  insert(src, 0, 9);
  display(src, 8);

  insert_better(src, 8);
  display(src, 8);
}
